package linkedlist;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class RemoveNthFromEnd {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        public static void printList(ListNode head){
            while(head!=null){
                System.out.print(head.val + "->");
                head = head.next;
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {

    }

    public ListNode removeNthFromEnd(ListNode head, int n) {



        ListNode preHead = new ListNode(0,head);
        ListNode slow = preHead;
        ListNode fast = head;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while(fast!=null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return preHead.next;
    }
    public boolean isValid(String s) {
        if(s.length()%2==1){
            return false;
        }
        Map<Character,Character> pairs = new HashMap<>();
        pairs.put(')','(');
        pairs.put(']','[');
        pairs.put('}','{');

        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            if(pairs.containsKey(s.charAt(i))){
                if(stack.isEmpty() || stack.peek() !=pairs.get(s.charAt(i))){
                    return false;
                }else{
                    stack.pop();
                }
            }else{
                stack.push(s.charAt(i));
            }
        }
        return stack.isEmpty();
    }


}
